package com.douma.practice;


public class MergeSort {

    private int[] data;

    public void sort(int[] data) {
        this.data = data;
        dfs(0, data.length - 1);
    }

    private void dfs(int start, int end) {
        if (start == end) return;

        int mid = (start + end) / 2;

        dfs(start, mid);
        dfs(mid + 1, end);

        // 合并排序
        merge(start, mid, end);
    }

    private void merge(int start, int mid, int end) {
        int[] tmp = new int[start - end + 1];
        int i = start;
        int j = mid + 1;
        int tmpPos = 0;

        // 将左边和右边的元素按照顺序拷贝到临时的数组中
        while (i <= mid && j <= end) {
            if (data[i] < data[j]) {
                tmp[tmpPos++] = data[i++];
            } else {
                tmp[tmpPos++] = data[j++];
            }
        }

        // 如果左边还有元素，则直接将左边的元素拷贝到临时数组
        while (i <= mid) {
            tmp[tmpPos++] = data[i++];
        }

        // 如果右边还有元素，则直接将右边的元素拷贝到临时数组
        while (j <= end) {
            tmp[tmpPos++] = data[j++];
        }

        // 拷贝
        for (int k = 0; k < tmp.length; k++) {
            data[start++] = tmp[k];
        }
    }


}
